Businesses and consumers rely on information processing infrastructures for accessing and sharing information. The information or data is often organized and kept in records for ease of access by multiple users or applications. When the collection of information is organized in electronically accessible records, it is managed and updated by computers. These electronically accessible records can be indexed and stored into operational databases. However, standard query languages are generally suitable for single dimensional data. For example, for a database containing building locations, a two dimensional index may be built to cover a region. For each building a two dimensional coordinate may be built that identifies the building in terms of its latitude and longitude. A query for a building is then answered by a database management system by creating two slices (one for covering longitudinal range and one for covering latitudinal range) and intersecting the two results. This approach is highly inefficient as the processing is multiplied by the number of dimensions.
Another approach is to create cells by overlaying a uniform grid over the range of data. Objects that lie within a cell are then assigned to that cell. In order to retrieve an object within a cell, all objects within a range of grids are retrieved and subjected to a brute-force search. However, this method is not workable if the data itself is not uniformly distributed. For example, if a cell size of one mile by one mile (1×1) is selected, there may be too many buildings in a 1×1 cell in an urban area making it impractical for brute force search. Furthermore, cells for other areas (e.g., rural areas) may be empty or virtually empty. Indexing and storing empty cells requires storage space and decreases the efficiency of the index table.